package com.michael.leetcode;

import org.junit.Test;

public class RotateRight_61 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    /**
     * 61. 旋转链表
     * 中等 相关标签 相关企业
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     * 示例 1：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[4,5,1,2,3]
     * 示例 2：
     * <p>
     * <p>
     * 输入：head = [0,1,2], k = 4
     * 输出：[2,0,1]
     * 提示：
     * 链表中节点的数目在范围 [0, 500] 内
     * -100 <= Node.val <= 100
     * 0 <= k <= 2 * 109
     */

    // 方法一
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode temp = head;
        // 先求长度
        int l = 1;
        while (temp.next != null) {
            l++;
            temp = temp.next;
        }
        // 求最后要反转的个数 
        int c = l - k % l;
        if (c == l) {
            return head;
        }
        // 双指针找到分割点
        int index = 0;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && index <= c) {
            slow = fast;
            fast = fast.next;
            index++;
        }

        // 拼接
        slow.next = null;
        temp = fast;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = head;
        return fast;
    }
    
    @Test
    public void test() {
        ListNode temp = new ListNode(0);
        for (int i = 2; i > 0; i--) {
            ListNode head = new ListNode(i);
            head.next = temp;
            temp = head;
        }

        ListNode listNode = rotateRight(temp, 4);

        System.out.println(listNode);
    }
    
    
    // 方法二 两次反转
    public ListNode rotateRight1(ListNode head, int k) {
        
        
        return null;
    }


    // 超时了
    public ListNode rotateRight2(ListNode head, int k) {
        for (int i = 0; i < k; i++) {
            head = rotate(head);
        }
        return head;
    }

    private ListNode rotate(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null) {
            slow = fast;
            fast = fast.next;

        }
        slow.next = null;
        fast.next = head;
        return fast;
    }


    @Test
    public void test1() {
        ListNode temp = new ListNode(0);
        for (int i = 2; i > 0; i--) {
            ListNode head = new ListNode(i);
            head.next = temp;
            temp = head;
        }

        ListNode listNode = rotateRight2(temp, 4);

        System.out.println(listNode);
    }


}